#
# @lc app=leetcode.cn id=74 lang=python3
#
# [74] 搜索二维矩阵
#

# @lc code=start
from typing import List
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])

        def posToRank(i, j):
            return i*n+j
        def rankToPos(k):
            return (k//n, k%n)
        
        l, r = 0, m*n-1
        while l<=r:
            med = (l+r)//2
            x, y = rankToPos(med)
            # print(l, r, med, x, y)
            if matrix[x][y]==target:
                return True
            elif matrix[x][y]<target:
                l = med+1
            else:
                r = med-1
        return False
# @lc code=end

